With the advance of information technology in recent years, the problem of searching and retrieval of data records has been encountered in many different application areas. While the technology of string-based search has matured over the years, the search of multi-dimensional space remains an area of active research. In particular, web-based maps and mobile maps in cell phones have been popularized in recent years. These mapping technologies call for efficient systems to support geographic search of points of interest over geographic space. Multi-dimensional search also has applications in domains such as similarity search of database records, pattern recognition, near neighbor search, and matching problems.